package code2;

import java.util.TreeMap;

/**
 * @author noob
 * @version 1.0
 * @date 2021/3/21 21:05
 */
public class HashTable<K,V> {
    public static final int upperTol = 10;
    public static final int lowerTol = 2;
    public static final int initCapacity = 7;




    private TreeMap<K,V>[] hashTable;
    private int M;
    private int size;


    public HashTable(int M){
        this.M = M;
        size = 0;
        hashTable = new TreeMap[M];
        for (int i = 0; i < M; i++) {
            hashTable[i] = new TreeMap<>();
        }
    }

    public HashTable() {
        this(initCapacity);
    }

    private int hash(K key){
        return (key.hashCode() & 0x7fffffff) % M;
    }


    public int getSize(){
        return  size;
    }

    public void add(K key,V value){
        TreeMap<K,V> map = hashTable[hash(key)];

        if(map.containsKey(key)){
            map.put(key,value); //覆盖
        }else{
            //没有就添加
            map.put(key,value);
            size++;

            if(size >= upperTol * M){
                resize(2*M);
            }

        }
    }


    public V remove(K key){
        TreeMap<K,V> map = hashTable[hash(key)];
        V ret = null;
        if(map.containsKey(key)){
            ret = map.remove(key);
            size--;

            if(size < lowerTol * M && M/2 >initCapacity){
                resize(M / 2);
            }
        }
        return ret;
    }

    private void resize(int newM) {
        TreeMap<K,V>[]  newHashTable = new TreeMap[newM];
        for (int i = 0; i < newM; i++) {
            newHashTable[i] = new TreeMap<>();
        }


        int oldM = M;
        this.M = newM;   //取模需要使用新的newM
        for (int i = 0; i < oldM; i++) {
            TreeMap<K,V> map = hashTable[i];
            for(K key: map.keySet()){
                newHashTable[hash(key)].put(key,map.get(key));
            }
        }
        this.hashTable = newHashTable;

    }


    public void set(K key,V value){
        TreeMap<K,V> map = hashTable[hash(key)];
        if(!map.containsKey(key)){
            throw  new IllegalArgumentException(key+" doesn't exist!");
        }
        map.put(key,value);
    }

    public boolean contains(K key){
        return hashTable[hash(key)].containsKey(key);
    }

    public V get(K key){
       return   hashTable[hash(key)].get(key);
    }



}
